\section{Introducción}
Este problema trata de obtener el costo mínimo al cortar un listón de madera en varias partes. El costo de cada corte es proporcional al largo de cada segmento a cortar.
\section{Desarrollo}

\subsection{Idea General del Algoritmo}
El algoritmo que resuelve este problema esta diseñado usando la técnica de \textit{Programación dinámica} el cual retorna una secuencia de cortes, es decir, el orden en que deben realizarse estos para minimizar el costo. 
Este algoritmo se basa en soluciones a subproblemas del problema original para generar la solución final. El estado final del listón, con los cortes realizados, es independiente del orden de los mismos.
La solución se genera tras elegir, de la secuencia de entrada, un corte inicial y evaluar el costo óptimo de la secuencias generadas tras partir la original en dos al elegir dicho corte.

\subsection{Correctitud}
%2-Justificar por que el procedimiento explicado en el primer punto resuelve efectivamente el problema.
Si tenemos 3 cortes, sea $p_i$ el corte que elegimos realizar primero, ubicado en la posición $i$ de la secuencia de entrada. En principio tenemos $i$ para $1\ge i \ge 3$ candidatos. Por cada una de estas alternativas los demás cortes tienen dos opciones de orden\footnote{Junto con estas estaríamos generando todas las permutaciones de los 3 elementos.}. Se puede ver que no necesitamos estas dos opciones sino la que es óptima. Por ende la solución final se arma ubicando el corte $p_i$ y los cortes restantes ordenados de manera óptima. Si llamamos $q$ al largo, luego de ubicar $p_i$ necesitamos la solución óptima para los cortes entre $0$ y  $p_i$ y para los que están comprendidos entre $p_i$ y $q$. Estas son subsoluciones de la instancia original, ya que son menores que esta; tienen menor cantidad de cortes y menor longitud del listón\footnote{De hecho, el conjunto de cortes de las subsoluciones son subconjuntos del conjunto de cortes de la solución original.}. Basado en esto se generó la siguiente función recursiva:

\begin{equation}
     \label{eq:recursiva}
costo(a,b) = \left\{
	       \begin{array}{ll}
			 0      & \mathrm{para\ }  b>a ; b-a = 1 \\
			 C(b)-C(a) + MIN_{(a < i < b)}(costo(a,i)+costo(i,b))    & \mathrm{para\ } b>a ; b-a \ge 2
	       \end{array}
	     \right.
 \end{equation}
 
 Siendo $a$, el índice al inicio del intervalo, $b$, el índice al final\footnote{Estos índices corresponden a la secuencia $S = \{c_0,c_1,..,c_{n-1},c_n\}$ donde $c_i$ para $1 \ge i \ge n-1$ es el corte $i$ en la secuencia de entrada. $c_0=0$ y $c_n=largo$ son los cortes que definen el listón inicial.} y $C(i)$ el corte en la posición $i$ de la secuencia de entrada. Si $b-a=1$  significa que no hay cortes para realizar entre el inicio y el fin del intervalo\footnote{Porque el fin del intervalo se encuentra inmediatamente después del inicio.}, por lo que el costo es $0$. Si $b-a\ge2$  hay al menos un corte entre el inicio y el fin del intervalo y sabemos que independientemente del corte que se realice primero, el costo de este sera la longitud del intervalo, $C(b)-C(a)$, luego hay que sumarle el costo óptimo para las subsecuencias $(a,i)$ e $(i,b)$. Como estas corresponden al mismo problema pero con una instancia mas chica se llama recursivamente a $costo(a,i)$ y $costo(a,i)$.

\paragraph*{}
 Se puede ver en \ref{eq:recursiva} que para generar una solución se necesitan soluciones a problemas mas pequeños. Dado que $a < i < b$ entonces $costo(a,i)<costo(a,b)$ y $costo(i,b)<costo(a,b)$. Si en vez de utilizar la fórmula recursiva usamos la iterativa(basada en la anterior), podemos llenar una tabla, desde el caso base a casos mas grandes, asegurándonos de que en la posición $i,j$ se encuentre el valor de la llamada $costo(i,j)$.
 
 Esta tabla es de $n$ x $n$ siendo $n$ la longitud de la secuencia de entrada mas dos\footnote{Porque se agrega como primer elemento el inicio del intervalo $0$ y como último elemento el largo del listón}, se inicializa con los valores del caso base, todas las celdas donde se cumpla $j-i=1$ tendrán el valor $0$(Ver línea 3 en algoritmo \ref{alg:matriz}). Luego llenamos las celdas restantes en diagonales, calculando los valores con $j-i=x$ para $2 \le x <n$ donde para cada $x$ se representan los casos donde entre el inicio y el fin del intervalo haya $x-1$ cortes(Ver línea 5 en algoritmo \ref{alg:matriz}).
 
 Cabe aclarar que todos los índices utilizados en esta sección hacen referencia a una posición en la secuencia de entrada la cuál debe estar ordenada ascendentemente para que se cumpla el principio de optimalidad.
 
\subsection{Pseudocódigo}
En la línea 3 se inicializan los casos base. En la 5 se genera la iteración basada en la función \ref{eq:recursiva}. Este bucle indica la diferencia entre el índice del inicio y del fin de la subsolución a generar; si $delta=2$ significa que se generara una solucion donde solo hay un corte entre el inicio y el fin. El ciclo en 6 se repite tantas veces como subsoluciones de tamaño $delta$ haya en la solución final. Por último el ciclo en 9 evalúa que corte de la subsolución es conveniente hacer primero para minimizar el costo.

Se tienen dos matrices, una con los costos mínimos y otras con el índice del corte que se debe realizar primero; $costo[a][b]$ es el costo mínimo de la subsolución comprendida entre $a$ y $b$. $sol[a][b]$ contiene el índice del corte que es necesario realizar primero en la misma subsolución. Luego la solución final se genera tras recorrer la matriz $sol$ usando una pila como se muestra en el algoritmo \ref{alg:solucion}.
\begin{algorithm}
\caption{Llenado de la matriz de manera iterativa}
\label{alg:matriz}
\begin{algorithmic}[1]\parskip=1mm
\STATE $secuenciaEntrada \leftarrow 0+secuenciaEntrada+largo$ 
\STATE $n \leftarrow longitud(secuenciaEntrada)$


\FOR{$i = 0$ \textbf{hasta} $n-1$}
	\STATE $costo[i][i+1] \leftarrow 0$
\ENDFOR

\FOR{$delta = 2$ \textbf{hasta} $n$}
	\FOR{$inicio = 0$ \textbf{hasta} $n-delta$}
		\STATE $fin \leftarrow inicio+delta$
		\STATE $costo[inicio][fin]  \leftarrow -1$
		\FOR{$i = inicio+1$ \textbf{hasta} $fin$}
			\STATE $costoParcial \leftarrow cortes[fin]-cortes[inicio] + costo[inicio][i]+costo[i][fin]$
			\IF{$costo[inicio][fin] = -1$ or $costoParcial<costo[inicio][fin]$}
				\STATE $costo[inicio][fin] \leftarrow costoParcial$
				\STATE $sol[inicio][fin] \leftarrow i$
			\ENDIF
		\ENDFOR
	\ENDFOR
\ENDFOR
\end{algorithmic}
\end{algorithm}

\begin{algorithm}
\caption{Armado de la solución}
\label{alg:solucion}
\begin{algorithmic}[1]\parskip=1mm
\STATE $solucion \leftarrow$ secuencia vacía de tamaño cantidad de cortes
\STATE $pila \leftarrow TADPila()$
\STATE $tupla = Dupla()$
\STATE $tuplaTemp = Dupla()$
\STATE $tupla[0] \leftarrow 0$
\STATE $tupla[1] \leftarrow n-1$
\STATE $pila.apilar(tupla)$
\FOR{$i = 0$ \textbf{hasta} $n-2$}
	\STATE $tupla = pila.desapilar()$
	\STATE $indice \leftarrow sol[tupla[0]][tupla[1]]$
    \STATE $solucion[i] \leftarrow cortes[indice]$

	\IF{$indice<tupla[1]-1$}
		\STATE $tuplaTemp[0] = indice$
		\STATE $tuplaTemp[1] \leftarrow tupla[1]$
		\STATE $pila.apilar(tuplaTemp)$
	\ENDIF
	\IF{$indice>tupla[0]+1$}
		\STATE $tuplaTemp[0] \leftarrow tupla[0]$
		\STATE $tuplaTemp[1] \leftarrow indice$
        \STATE $pila.apilar(tuplaTemp)$
	\ENDIF
\ENDFOR
\STATE retornar $solucion$

\end{algorithmic}
\end{algorithm}


\subsection{Cota de complejidad temporal}
La complejidad temporal de este algoritmo es:
\begin{Large}
$$
\mathcal{O}(n^3)
$$
\end{Large}

%3-Encontrar una cota de complejidad temporal del algoritmo propuesto. Los parametros en funcion de los cuales dar la cota estan detallados en el problema. Utilizar el modelo uniforme salvo que se explicite lo contrario.

\subsection{Demostración de complejidad}
%4-Justificar por qu´ el algoritmo presentado en el primer punto cumple la cota de complejidad dada en el punto anterior.
En el algoritmo \ref{alg:matriz} tenemos tres ciclos anidados donde cada uno no se repite mas de $n$ veces lo que nos daría la cota antes nombrada. 

Para el armado de la solución vemos que el ciclo en la línea 8 del algoritmo \ref{alg:solucion} se repite tantas veces como cortes haya, no mas que $n$. Como estructura auxiliar usamos una pila cuya implementación en java nos garantiza una complejidad de $\mathcal{O}(1)$ para encolar y desencolar\footnote{Se desprende de la implementación de java.util.Stack y java.util.Vector en OpenJDK 6}.

Analizando con mas detalle, es necesario llenar la mitad de la matriz porque solo se utilizarán las celdas donde el índice de la fila es menor que el de la columna. Tampoco se usara la diagonal mayor, donde los índices de fila y columna son iguales(Ver línea 5 en algoritmo \ref{alg:matriz}). Por ende la cantidad de celdas a llenar es: 
\begin{equation}
\frac{n^2-n}{2}
\end{equation}
Por cada celda se realizarán a lo sumo $n-2$ iteraciones(Ver línea 9 en algoritmo \ref{alg:matriz})\footnote{$n$ es la longitud de la secuencia con el inicio y el fin incluidos. $n-2$ es la cantidad de cortes.}. Lo que resulta en:
\begin{equation}
\frac{n^2-n}{2}(n-2) = n^3-2n^2+n = f(x)
\end{equation}
El valor $n$ es la cantidad de cortes mas dos, dado que en la secuencia se incluyen el inicio y el fin del listón. Si definimos el tamaño de entrada como $N$ siendo esta la cantidad de cortes. Resulta:
\begin{equation}
(N+2)^3-2(N+2)^2+(N+2) = g(N)
\end{equation}
Sea $T(I)$ el costo temporal del algoritmo para la instancia $I$. Obtenemos:
$$
T(I) \in \mathcal{O}(N^3)
$$
\subsection{Casos de prueba de complejidad}
%8-Dar un conjunto de casos de test que permitan observar la performance en t´rminos de tiempo del problema. Para esto se deben desarrollar tanto tests patol´gicos de peor caso como tests generados sin una intencionalidad.
Para comprobar la complejidad se corrieron casos variando la cantidad de cortes, el largo del listón y los valores de cortes. Los datos que se usaron para generar el gráfico \ref{fig:costoXcorte} son de 10000 casos con largo entre 1 y 1000, cantidad y ubicación de cortes aleatoriamente.
Tambien se generaron 100000 casos con largo variable y cantidad de cortes fija, para verificar si el largo del listón afecta al costo temporal(Ver \ref{fig:costoXlargo}).


\subsection{Casos de prueba de correctitud}
Para comprobar la correctitud se generan casos patológicos y se evalúa el resultado del algoritmo.

\subsubsection*{Caso 1}
Sin cortes.
\begin{center}
\begin{large}
\texttt{largo: 10	cortes:-	solución:-}
\end{large}
\end{center}

\subsubsection*{Caso 2}
Un único corte.
\begin{center}
\begin{large}
\texttt{largo: 10	cortes:4	solución:4
}
\end{large}
\end{center}

\subsubsection*{Caso 3}
Dos cortes, donde las dos únicas posibilidades de orden tienen costos diferentes.
\begin{center}
\begin{large}
\texttt{largo: 10	cortes:3 5	solución:5 3}
\end{large}
\end{center}

\subsubsection*{Caso 4}
Dos cortes, donde las dos únicas posibilidades de orden tienen costos iguales.
\begin{center}
\begin{large}
\texttt{largo: 10	cortes:3 7	solución:3 7}
\end{large}
\end{center}

\subsubsection*{Caso 5}
Cortes aglomerados en un extremo. para que el costo sea mínimo es necesario realizar primero el corte mayor.
\begin{center}
\begin{large}
\texttt{largo: 10	cortes:1 3 4	solución:4 1 3}
\end{large}
\end{center}

\subsubsection*{Caso 6}
La distancia entre los cortes crece exponencialmente. Se puede apreciar que en este caso la solución es realizar los cortes de mayor a menor.
\begin{center}
\begin{large}
\texttt{largo: 512	cortes:2 4 8 16 32 64 128 256	solución:256 128 64 32 16 8 4 2}
\end{large}
\end{center}

\subsubsection*{Caso 7}
La distancia entre los cortes crece linealmente. En este caso la solución no es realizar los cortes de mayor a menor como lo fue en el caso anterior, a pesar de que en ambos, la distancia entre cortes es creciente.
\begin{center}
\begin{large}
\texttt{largo: 210	cortes:10 30 60 100 150	solución:100 60 30 10 150}
\end{large}
\end{center}

\subsubsection*{Caso 8}
La distancia entre los cortes es constante. Se puede apreciar que una vez elegido el primer corte, se eligen siguientes de manera tal que el próximo corte se realice en un segmento con la menor longitud posible, se van intercalando, realizando el $i-1$ e $i+1$ antes de realizar el $i$.
\begin{center}
\begin{large}
\texttt{largo: 100	cortes:10 20 30 40 50 60 70 80 90	solución:40 20 10 30 60 50 80 70 90}
\end{large}
\end{center}

\subsubsection*{Caso 9}
Este caso puede ser engañoso. Uno podría sacar la conclusión de que la solución óptima proviene de elegir el corte central primero y generalizar para todos los casos del mismo tipo. Esto sería un error, porque a pesar de que en el caso anterior los cortes también son equidistantes, el primer corte no es el central sino uno cercano.
\begin{center}
\begin{large}
\texttt{largo: 100	cortes:25 50 75	solución:50 25 75}
\end{large}
\end{center}


\section{Resultados}
%9-Presentar en forma de gr´fico la comparaci´n entre tiempo estimado de corrida seg´n la complejidad temporal calculada, tiempo medido de corrida para los tests patol´gicos de peor caso, y tiempo medido de corrida para los tests sin intencionalidad.
Como se puede apreciar en la figura \ref{fig:costoXcorte}, la cantidad de cortes es la que rige el costo temporal del algoritmo. La función graficada es $an^3+b$ los costos medidos son en nanosegundos y se tomó el mínimo entre todas las instancias con el mismo tamaño. Se ve como la función acota el tiempo del algoritmo en función del tamaño de entrada. 


\begin{minipage}{\linewidth}
		\makebox[\linewidth]{
\includegraphics[width=15cm]{prob3/graficos/costoXcortes.pdf}
		}
		\captionof{figure}{Performance en función de la cantidad de cortes.}
		\label{fig:costoXcorte}
	\end{minipage}	 

\paragraph*{} 
En el gráfico \ref{fig:costoXlargo} se evidencia que la variación del largo del listón no afecta al costo temporal del algoritmo, con lo cual podemos ratificar que el tamaño de la entrada es la cantidad de cortes.


\begin{minipage}{\linewidth}
		\makebox[\linewidth]{
\includegraphics[width=15cm]{prob3/graficos/costoXlargo.pdf}
		}
		\captionof{figure}{Performance en función del largo del listón.}
		\label{fig:costoXlargo}
	\end{minipage}	 
\section{Conclusiones}
Este problema ha planteado un desafío para nosotros al tener que identificar el \textit{principio de optimalidad} así también como los subproblemas y subsoluciones de una instancia.

Lo primero que logramos fue encontrar una solución recursiva el problema, luego notamos que las llamadas recursivas se repetían. Para evitar esto, generamos una matriz y la llenamos de a diagonales basándonos en la solución recursiva.

Se llegó a una solución mucho mas eficiente ya que si resolvemos el problema verificando todas las soluciones, la complejidad sería $\mathcal{O}(!n)$.
